package binarysearch;

/**
 * 针对题意灵活使用两种边界分法  本题应该是【l ~ mid -1】, 【mid, r】分法  对应求整数的下边界
 *
 * 两种分法
 *
 * int mid = (l + r + 1) >> 1    【l ~ mid -1】, 【mid, r】   因为 如 l = 2  r = 3  此时 mid = 2 无限循环
 * int mid = (l + r ) >> 1       【l ~ mid】, 【mid + 1, r】
 */
public class 求平方根_69 {

    class Sqrtx_69 {
        public int mySqrt(int x) {
            if(x < 2) return x; // 0 or 1
            int l = 1, r = x; // 输入x=0的时候返回0
            while(l < r) {   // 使用l < r 而不是 l<=r 能保证最终 l == r 返回 l 或 r 都是正确的
                int mid = (l + r + 1) >> 1;
                // 不用  (long)mid * mid <= x 来防止整型溢出  用除法好些
                // 按照题意   平方  只能小于等于x  大于x 整数一定不对  加上小数就更大了
                // 使用如下分边界方法
                //       【l ~ mid -1】, 【mid, r】  如果是 【l ~ mid】, 【mid + 1, r】 最终只会是 将l变成 mid + 1  如 x = 8 求出来  l = r = 3 不满足
                // 但是这种分界方法  存在  l= 2 r=3 时的  l = mid  = 2  死循环    需要求mid的时候 + 1             int mid = (l + r + 1) >> 1;
                // 如果是 【l ~ mid】, 【mid + 1, r】 就不需要 求mid的时候 +1                                    int mid = (l + r ) >> 1;

                if(x / mid >= mid) {
                    l = mid  ;            // 二分左边界一定不能改为mid  死记住
                    // 额外使用ans保存mid而不是l的原因时如果这里 l = mid  会导致最后  （4 + 5 ）/2 = 4 无限循环
                } else {
                    r = mid - 1;
                }
            }
            return l;
        }
    }
}
